ON THE LOWER BOUND OF THE SHANNON FUNCTION
FOR READ-MANY CERTIFICATE LENGTH IN ONE BASE FAMILY 

Kaftan Daria Vladimirovna, Postgraduate student, Moscow State University named after M. V. Lomonosov (1 Leninskie gory street, Moscow, Russia), blond.programmist@gmail.com

517.718.7

Background. The research of various properties of Boolean functions is an actual problem in connection with the progress of informatics and digital technology. The ability of a function to be represented in a given basis via a formula without replication of variables (a read-once formula) is an important one. The class of functions having this ability may be regarded as a class of “simple” functions in this basis. The author considers a problem of finding a read-many certificate for an arbi-trary Boolean function in the extended elementary basis with a discriminator func-tion of s variables. The object of the article is to improve the lower bound of the Shannon function for read-once certificate length in this basis.
Materials and methods. The method named “the matrix of various values” is applied in this paper to a well-selected read-many function with a high lower bound of a read-many certificate.
Results and conclusion. The author shows that the length of s read-many certifi-cate of a function, which equals to 1 only on the sets (0,…,0) and (1,…,1), is not less than n/2 – s + 1 in this basis. Thus, the researcher has improved the known lower bound n/s of Shannon function for the certificate length in this basis.

read-once function, read-many certificate, discriminator function, matrix of various values.

1. Shannon C. E. Trans. 1938, AIEE 57, pp. 713–723.
2. Stetsenko V. A. Matematicheskie voprosy kibernetiki [Mathematical problems of cybernetics]. Issue 4. Moscow: Fizmatlit, 1992, pp. 139–177.
3. Chistikov D., Fedorova V., Voronenko A. Fundamenta Informaticae. 2014, no. 132 (1), pp. 63–77.
4. Voronenko A. A., Fedorova V. S., Chistikov D. V. Izvestiya vuzov. Matematika [University proceedings. Mathematics]. 2011, no. 11, pp. 72–77.
5. Voronenko A. A. Vestnik Moskovskogo universiteta. Ser. 15. Vychislitel'naya matematika i kibernetika [Bulletin of Moscow University. Series 15. Calculus mathematics and cybernetics]. 2013, no. 4, pp. 45–47.
6. Voronenko A. A. Prikladnaya diskretnaya matematika [Applied discrete mathematics]. 2011,no.3(13),pp.12–16.